 class MyLinkList {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;


    public int size(){
        int count=0;
        ListNode cur=head;
        while (cur!=null){
            cur=cur.next;
            count++;
        }
        return count;
    }

    public void display(){
        ListNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
     //查找是否包含关键字key是否在双链表当中
    public boolean contains(int key){
        ListNode cur=head;
        while (cur!=null){
            if (cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    //头插法
    public void addFirst(int val){
        ListNode listNode=new ListNode(val);
        if (head==null){
            head= last=listNode;

        }
        else {
            listNode.next= head;
            head.prev=listNode;
            head=listNode;
        }
    }

    //尾插法
    public void addLast(int val){
        ListNode listNode=new ListNode(val);
        if (head==null){
            head=last=listNode;
        }
        else {
            last.next=listNode;
            listNode.prev=last;
            last=listNode;
        }
    }
private void checkIndex(int index){
     if (index<0||index>size()){
         throw new IndexNotLegalException("双向列表插入下标不合法");
     }
}
private  ListNode findIndex(int index){
    ListNode cur=head;
    while (index!=0){
        cur=cur.next;
        index--;
    }
    return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int val){
        try {
            checkIndex(index);
        }catch (Exception e){
            e.printStackTrace();
        }
        if (index==0){
            addFirst(index);
            return;
        }
        if (index==size()){
            addLast(index);
            return;
        }
        ListNode cur=findIndex(index);
        ListNode listNode=new ListNode(val);
        listNode.next=cur;
        cur.prev.next=listNode;
        listNode.prev=cur.prev;
        cur.prev=listNode;
    }
private ListNode findValIsKeyListNode(int key){
    ListNode cur=head;
    while (cur!=null){
        if (cur.val==key){
            return cur;
        }
        cur=cur.next;
    }
    return null;
}
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        ListNode cur=head;
        while (cur!=null){
            if (cur.val==key){
                if (cur==head){
                    head=cur.next;
                    if (head!=null){
                        head.prev=null;
                    }else {
                        //head==null
                        last = null;
                    }
                }
                else if (cur==last){
                    last=cur.prev;
                    last.next=null;

                }
                else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                return;
            }
            cur=cur.next;
        }

    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        ListNode cur=head;
        while (cur!=null){
            if (cur.val==key){
                if (cur==head){
                    head=cur.next;
                    if (head!=null){
                        head.prev=null;
                    }else {
                        //head==null
                        last = null;
                    }
                }
                else if (cur==last){
                    last=cur.prev;
                    last.next=null;

                }
                else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur=cur.next;
        }

    }


    public void clear(){
        //法一
//        head=null;
//        last=null;
        //法二
        ListNode cur=head;
        while (cur!=null){
            ListNode curNext=cur.next;
            cur.prev=null;
            cur.next=null;
            cur=curNext;
        }
        head=last=null;
    }

}

   public class MyLinkListText{
       public static void main(String[] args) {
           MyLinkList myLinkList=new MyLinkList();
           myLinkList.addLast(4);
           myLinkList.addLast(5);
           myLinkList.addLast(6);
           myLinkList.addIndex(1,99);
           myLinkList.display();
           myLinkList.remove(4);
           myLinkList.display();
       }
   }